#include <iostream>
#include <cstdlib>
template <typename T>
class Node
{
public:
T data;
Node<T>* lc;
Node<T>* rc;
Node<T>* parent;
Node(T _data);
};


template <typename T>
class BinaryTree
{
private:
    Node<T>* root;
    void inordertreewalk(Node<T>* _x) const;
    void release(Node<T>* _x);
    Node<T>* search(Node<T>* _x,T _data);
    
public:
    BinaryTree() {root = NULL;};
    BinaryTree(T _data);
    ~BinaryTree();
    void insert(T _data);
    void inorder_treewalk() const;
    void test_successor();
    Node<T>* min(Node<T>* _x) const;
    Node<T>* max(Node<T>* _x) const;
    Node<T>* successor(Node<T>* _x) const;
    Node<T>* predecessor(Node<T>* _x) const;
    Node<T>* tree_search(T _data);
    void BSTSORT(T* _A, int n);
    Node<T>* transplant(Node<T>* u,Node<T>* v);
    Node<T>* tree_delete(Node<T>* z);
};



template <typename T>
BinaryTree<T>::BinaryTree(T _data)
{
    Node<T>* m = new Node<T>(_data);
    if (root == NULL)
    root = m;
};



template <typename T>
void BinaryTree<T>::release(Node<T>* _x)
{
    if (_x != NULL)
    {
    release(_x->lc);
    release(_x->rc);
    delete _x;
    }
};


template <typename T>
BinaryTree<T>::~BinaryTree()
{
    release(root);
};


template <typename T>
Node<T>::Node(T _data)
{
    data = _data;
    parent = lc = rc = NULL;
};


template <typename T>
Node<T>* BinaryTree<T>::min(Node<T>* _x) const
{
    while (_x->lc != NULL)
    _x = _x->lc;
    return _x;
};


template <typename T>
Node<T>* BinaryTree<T>::max(Node<T>* _x) const
{
    while (_x->rc != NULL)
    _x = _x->rc;
    return _x;
};


template <typename T>
Node<T>* BinaryTree<T>::successor(Node<T>* _x) const
{
    Node<T>* x = _x;
    if (x->rc != NULL)
         return min(x->rc);
    Node<T>* y = x->parent;
    while (y != NULL && x == y->rc)
    {
      x = y;
      y = y->parent;
    }
    return y;
};



template <typename T>
Node<T>* BinaryTree<T>::predecessor(Node<T>* _x) const
{
  Node<T>* x = _x;
  if(x->lc != NULL)
      return max(x->lc);
  Node<T>* y = x->parent;
  while(y != NULL && x == y->lc)
  {
     x = y;
     y = y->parent;
  }
  return y;
};


template <typename T>
void BinaryTree<T>::insert(T _data)
{
    Node<T>* y = NULL;
    Node<T>* x = root;
    Node<T>* z = new Node<T>(_data);
    while (x != NULL)
    {
    y = x;
    if (z->data  < x->data)
        x = x->lc;
    else x = x->rc;
    }
    z->parent = y;
    if (y == NULL)
    root = z;
    else if (z->data < y->data)
    y->lc = z;
    else y->rc = z;
};


template <typename T>
Node<T>* BinaryTree<T>::search(Node<T>* _x,T _data)
{
  if(_x == NULL || _data == _x->data)
    return _x;
  if(_data < _x->data)
  return search(_x->lc,_data);
  else return search(_x->rc,_data);
}

template <typename T>
Node<T>* BinaryTree<T>::tree_search(T _data)
{
  return search(root,_data);
}


template <typename T>
void BinaryTree<T>::inordertreewalk(Node<T>* _x) const
{
    if (_x != NULL)
    {
    inordertreewalk(_x->lc);
    std::cout << _x->data << "  ";
    inordertreewalk(_x->rc);
    }
};

template <typename T>
void BinaryTree<T>::inorder_treewalk() const
{
    inordertreewalk(root);
    std::cout << std::endl;
};


template <typename T>
void BinaryTree<T>::BSTSORT(T* _A, int n)
{
 BinaryTree<T> A;
 for(int i=0; i<n; i++)
 A.insert(_A[i]);
 A.inorder_treewalk();
}


template <typename T>
Node<T>* BinaryTree<T>::transplant(Node<T>* u,Node<T>* v)
{
	if (u->parent == NULL)
	  root = v;
	else if (u == u->parent->lc)
	  u->parent->rc = v;
	else u->parent->rc == v;
    if (v != NULL)
      v->parent = u->parent;
	
}


template <typename T>
Node<T>* BinaryTree<T>::tree_delete(Node<T>* z)
{
	Node<T>* y;
	if (z->lc == NULL)
	  transplant(z,z->rc);
	else if (z->rc == NULL)
	  transplant(z,z->lc);
	else y = min(z->rc);
	if (y->parent != z)
	{
		transplant(y,y->rc);
		y->rc = z->rc;
		y->rc->parent = y;
	}
	transplant(z,y);
	y->lc = z->lc;
	y->lc->parent = y;
}
